9615. Frobenius coin problem

 

Given two coins of denominations x and y respectively. Find the largest amount S that cannot be obtained using these two coins (assuming infinite supply of coins) and the total number T of such non obtainable amounts. If no such value exists print “NA”.

 

Input. Two positive integers x and y (1 < x, y ≤ 109).

 

Output. Print in one line two numbers: S and T.

 

Sample input 1

Sample output 1

2 5

3 2

 

 

Sample input 2

Sample output 2

5 10

NA

 

 

SOLUTION

coins exchange

 

Algorithm analysis

If GCD(x, y) > 1, then there are an infinite number of sums that cannot be paid with two denominations. In this case, print “NA”.

The largest sum S that cannot be paid with denominations x and y is x * y – x – y.

The total number T of sums that are not representable by the available coins is (x – 1) * (y – 1) / 2.

 

Example

Consider the sample x = 2, y = 5. In ths case

S = 2 * 5 – 2 – 5 = 3,

T = 1 * 4 / 2 = 2

The non-representable sumss are 1 and 3 (two sums).

 

Algorithm realization

Function gcd computes the greatest common divisor of numbers a and b.

 

long long gcd(long long a, long long b)

{

  return (!b) ? a : gcd(b, a % b);

}

 

The main part of the program. Read the input data.

 

scanf("%lld %lld", &x, &y);

 

If GCD(x, y) > 1, then there are an infinite number of sums that cannot be paid with two denominations.

 

if (gcd(x, y) > 1)

{

  puts("NA");

  return 0;

}

 

s = (x * y) - x - y;

t = (x - 1) * (y - 1) / 2;

printf("%lld %lld\n", s, t);